package nachos.threads;

import nachos.machine.*;

import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * A scheduler that chooses threads based on their priorities.
 *
 * <p>
 * A priority scheduler associates a priority with each thread. The next thread
 * to be dequeued is always a thread with priority no less than any other
 * waiting thread's priority. Like a round-robin scheduler, the thread that is
 * dequeued is, among all the threads of the same (highest) priority, the thread
 * that has been waiting longest.
 *
 * <p>
 * Essentially, a priority scheduler gives access in a round-robin fassion to
 * all the highest-priority threads, and ignores all other threads. This has the
 * potential to starve a thread if there's always a thread waiting with higher
 * priority.
 *
 * <p>
 * A priority scheduler must partially solve the priority inversion problem; in
 * particular, priority must be donated through locks, and through joins.
 */
public class PriorityScheduler extends Scheduler {

    /**
     * Allocate a new priority scheduler.
     */
    public PriorityScheduler() {
    }

    /**
     * Allocate a new priority thread queue.
     *
     * @param	transferPriority	<tt>true</tt> if this queue should transfer
     * priority from waiting threads to the owning thread.
     * @return	a new priority thread queue.
     */
    public ThreadQueue newThreadQueue(boolean transferPriority) {
        return new PriorityThreadQueue(transferPriority);
    }

    public int getPriority(KThread thread) {
        Lib.assertTrue(Machine.interrupt().disabled());

        return getThreadState(thread).getPriority();
    }

    public int getEffectivePriority(KThread thread) {
        Lib.assertTrue(Machine.interrupt().disabled());

        return getThreadState(thread).getEffectivePriority();
    }

    public void setPriority(KThread thread, int priority) {
        Lib.assertTrue(Machine.interrupt().disabled());

        Lib.assertTrue(priority >= priorityMinimum
                && priority <= priorityMaximum);

        getThreadState(thread).setPriority(priority);
    }

    public boolean increasePriority() {
        boolean intStatus = Machine.interrupt().disable();

        KThread thread = KThread.currentThread();

        int priority = getPriority(thread);
        if (priority == priorityMaximum) {
            return false;
        }

        setPriority(thread, priority + 1);

        Machine.interrupt().restore(intStatus);
        return true;
    }

    public boolean decreasePriority() {
        boolean intStatus = Machine.interrupt().disable();

        KThread thread = KThread.currentThread();

        int priority = getPriority(thread);
        if (priority == priorityMinimum) {
            return false;
        }

        setPriority(thread, priority - 1);

        Machine.interrupt().restore(intStatus);
        return true;
    }
    /**
     * The default priority for a new thread. Do not change this value.
     */
    public static final int priorityDefault = 1;
    /**
     * The minimum priority that a thread can have. Do not change this value.
     */
    public static final int priorityMinimum = 0;
    /**
     * The maximum priority that a thread can have. Do not change this value.
     */
    public static final int priorityMaximum = 7;

    /**
     * Return the scheduling state of the specified thread.
     *
     * @param	thread	the thread whose scheduling state to return.
     * @return	the scheduling state of the specified thread.
     */
    protected ThreadState getThreadState(KThread thread) {
        if (thread.schedulingState == null) {
            thread.schedulingState = new ThreadState(thread);
        }

        return (ThreadState) thread.schedulingState;
    }

    /**
     * A <tt>ThreadQueue</tt> that sorts threads by priority.
     */
    protected class PriorityThreadQueue extends ThreadQueue {
        // inicio das modificações

        protected ThreadState so1_threadForaDaFila = null;
        protected PriorityQueue<ThreadState> so1_filaDePrioridade = new PriorityQueue<ThreadState>();
        //private java.util.PriorityQueue<ThreadState> so1_filaDePrioridade = new java.util.PriorityQueue<ThreadState>(8,new ThreadState<ThreadState>(this));

        PriorityThreadQueue(boolean transferPriority) {
            this.transferPriority = transferPriority;
        }

        public void waitForAccess(KThread thread) {
            Lib.assertTrue(Machine.interrupt().disabled());
            getThreadState(thread).waitForAccess(this);
        }

        public void acquire(KThread thread) {
            Lib.assertTrue(Machine.interrupt().disabled());
            getThreadState(thread).acquire(this);
        }

        public KThread nextThread() {
            Lib.assertTrue(Machine.interrupt().disabled());

            ThreadState so1_threadState = this.pickNextThread();
            so1_filaDePrioridade.remove(so1_threadState);
            if ((transferPriority != false) && (so1_threadState != null)) {
                //caso ache a thread
                this.so1_threadForaDaFila.removeQueue(this);
                so1_threadState.so1_espera = null;
                so1_threadState.addQueue(this);
            }
            this.so1_threadForaDaFila = so1_threadState;
            if (so1_threadState == null) {
                //caso não exista uma próxima thread
                this.so1_filaDePrioridade = new PriorityQueue<ThreadState>();
                return null;
            }
            //retorna a proxima thread
            return so1_threadState;
        }

        /**
         * Return the next thread that <tt>nextThread()</tt> would return,
         * without modifying the state of this queue.
         *
         * @return	the next thread that <tt>nextThread()</tt> would return.
         */
        protected ThreadState pickNextThread() {
            boolean so1_trava = Machine.interrupt().disable();

            this.so1_filaDePrioridade = new PriorityQueue<ThreadState>(so1_filaDePrioridade);

            Machine.interrupt().restore(so1_trava);
            return this.so1_filaDePrioridade.peek();
        }

        public void print() {
            Lib.assertTrue(Machine.interrupt().disabled());
            // implement me (if you want)
        }
        /**
         * <tt>true</tt> if this queue should transfer priority from waiting
         * threads to the owning thread.
         */
        public boolean transferPriority;
    }

    /**
     * The scheduling state of a thread. This should include the thread's
     * priority, its effective priority, any objects it owns, and the queue it's
     * waiting for, if any.
     *
     * @see	nachos.threads.KThread#schedulingState
     */
    //Comparable permite a comparação de instancias no java
    protected class ThreadState implements Comparable<ThreadState> {

        public long so1_idade = Machine.timer().getTime();
        protected LinkedList<PriorityQueue> so1_estaNaFila;
        protected int so1_prioridadeEfetiva;
        protected PriorityQueue so1_espera;

        /**
         * Allocate a new <tt>ThreadState</tt> object and associate it with the
         * specified thread.
         *
         * @param	thread	the thread this state belongs to.
         */
        public ThreadState(KThread thread) {
            this.thread = thread;
            //initialize the onQueue linkedlist
            this.so1_estaNaFila = new LinkedList<PriorityQueue>();
            this.so1_idade = Machine.timer().getTime();
            this.so1_prioridadeEfetiva = priorityDefault;
            this.so1_espera = null;
        }

        /**
         * Return the priority of the associated thread.
         *
         * @return	the priority of the associated thread.
         */
        public int getPriority() {
            return priority;
        }

        /**
         * Return the effective priority of the associated thread.
         *
         * @return	the effective priority of the associated thread.
         */
        public void calcEffectivePriority() {
            // implement me
            int so1_PrioridadeAnt = this.getPriority();
            int max = so1_PrioridadeAnt;
            if (so1_estaNaFila.size() > 0) {
                int tam = so1_estaNaFila.size();
                for (int i = 0; i < tam; i++) {
                    PriorityQueue so1_atual = so1_estaNaFila.get(i);
                    ThreadState so1_doador = so1_atual.pickNextThread();
                    if (so1_doador != null) {

                        if ((so1_doador.getEffectivePriority() > max) && so1_atual.transferPriority) {
                            max = so1_doador.getEffectivePriority();
                        }
                    }

                }
            }
            this.so1_prioridadeEfetiva = max;

        }

        public int getEffectivePriority() {
            return this.so1_prioridadeEfetiva;
        }

        /**
         * Set the priority of the associated thread to the specified value.
         *
         * @param	priority	the new priority.
         */
        public void setPriority(int priority) {
            this.priority = priority;
            this.calcEffectivePriority();
            if (this.so1_espera != null && (this.so1_espera.so1_threadForaDaFila != null)) {
                this.so1_espera.so1_threadForaDaFila.calcEffectivePriority();
            }

            // implement me
        }

        /**
         * Called when <tt>waitForAccess(thread)</tt> (where <tt>thread</tt> is
         * the associated thread) is invoked on the specified priority queue.
         * The associated thread is therefore waiting for access to the resource
         * guarded by <tt>waitQueue</tt>. This method is only called if the
         * associated thread cannot immediately obtain access.
         *
         * @param	waitQueue	the queue that the associated thread is now waiting
         * on.
         *
         * @see	nachos.threads.ThreadQueue#waitForAccess
         */
        public void waitForAccess(PriorityThreadQueue waitQueue) {
            Lib.assertTrue(Machine.interrupt().disabled());

            long time = Machine.timer().getTime();
            this.so1_idade = time;

            waitQueue.so1_filaDePrioridade.add(this);

            this.so1_espera = waitQueue;
            this.calcEffectivePriority();
        }

        /**
         * Called when the associated thread has acquired access to whatever is
         * guarded by <tt>waitQueue</tt>. This can occur either as a result of
         * <tt>acquire(thread)</tt> being invoked on <tt>waitQueue</tt> (where
         * <tt>thread</tt> is the associated thread), or as a result of
         * <tt>nextThread()</tt> being invoked on <tt>waitQueue</tt>.
         *
         * @see	nachos.threads.ThreadQueue#acquire
         * @see	nachos.threads.ThreadQueue#nextThread
         */
        public void acquire(PriorityThreadQueue waitQueue) {
            Lib.assertTrue(Machine.interrupt().disabled());
            Lib.assertTrue(waitQueue.priorityQueue.isEmpty());

            waitQueue.so1_threadForaDaFila = this;
            this.addFila(waitQueue);
            this.calcEffectivePriority();
        }

        public int compareTo(ThreadState status) {
            //changed first if from > to <
            if (status == null) {
                return -1;
            }
            if (this.getEffectivePriority() < status.getEffectivePriority()) {
                return 1;
            } else {
                if (this.getEffectivePriority() > status.getEffectivePriority()) {
                    return -1;
                } else {
                    if (this.so1_idade >= status.so1_idade) {
                        return 1;
                    } else {
                        return -1;
                    }
                }
            }
        }

        public void removeQueue(PriorityThreadQueue queue) {
            so1_estaNaFila.remove(queue);
            this.calcEffectivePriority();
        }

        public void addQueue(PriorityThreadQueue queue) {
            so1_estaNaFila.add(queue);
            this.calcEffectivePriority();
        }
        /**
         * The thread with which this object is associated.
         */
        protected KThread thread;
        /**
         * The priority of the associated thread.
         */
        protected int priority;
    }
}
